Introduction

• Many patterns in number theory come from repeating an operation and watching what happens.
• In modular arithmetic, multiplying a number by itself again and again eventually starts to cycle.
• A natural question emerges:
  How many times must you multiply a number by itself (mod $n$) before you get back to $1$?
• This number is called the order of the integer (mod $n$).

Repeated Multiplication and the Idea of “Coming Back to 1”

• Start with a number $a$ and multiply it by itself repeatedly:
  • $a^1 = a$
  • $a^2 = a \cdot a$
  • $a^3 = a \cdot a \cdot a$
• In ordinary arithmetic, these powers grow quickly.
• But modular arithmetic wraps numbers around, so powers may eventually return to $1$.
• Example (mod $7$):
  • $3^1 \equiv 3$
  • $3^2 \equiv 9 \equiv 2$
  • $3^3 \equiv 6$
  • $3^4 \equiv 18 \equiv 4$
  • $3^5 \equiv 12 \equiv 5$
  • $3^6 \equiv 15 \equiv 1$
  After 6 steps, we’re back at $1$.

Working in Modular Arithmetic

• Modular arithmetic focuses on remainders.
• We write $a \equiv b \pmod{n}$ if $a$ and $b$ leave the same remainder when divided by $n$.
• Multiplication behaves nicely:
  • If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then
    $ac \equiv bd \pmod{n}$.
• This makes repeated multiplication predictable and well‑behaved.

Units: The Numbers That Have Multiplicative Inverses

• Not every number has a multiplicative inverse modulo $n$.
• A number $a$ has an inverse mod $n$ iff $\gcd(a,n)=1$.
• Such numbers are called units modulo $n$.
• Only units can possibly have an order, because:
  • If $a$ has order $k$, then $a^k \equiv 1$, so $a$ must be invertible.

Defining the Order of an Integer Modulo $n$

• Let $a$ be a unit modulo $n$.
• The order of $a$ modulo $n$ is:
  • The smallest positive integer $k$ such that $$a^k \equiv 1 \pmod{n}.$$
• Key points:
  • The order always exists for units.
  • The order is always a positive integer.
  • The order measures the “cycle length” of repeated multiplication.

First Examples: Small Moduli, Clear Patterns

Example 1: Order of $2$ mod $5$

• $2^1 \equiv 2$
• $2^2 \equiv 4$
• $2^3 \equiv 8 \equiv 3$
• $2^4 \equiv 16 \equiv 1$

Order is 4.

Example 2: Order of $3$ mod $7$

• Computed earlier: order is 6.

Example 3: Order of $4$ mod $9$

• $\gcd(4,9)=1$, so order exists.
• $4^1 \equiv 4$
• $4^2 \equiv 16 \equiv 7$
• $4^3 \equiv 28 \equiv 1$

Order is 3.

Observations

• Orders vary widely.
• Some numbers have large orders, some small.
• The order always divides a special number called $\varphi(n)$.
  • $\varphi$ is the Greek letter "phi"

Why Orders Always Divide $\varphi(n)$

• $\varphi(n)$ is Euler’s totient function:
  number of integers between $1$ and $n$ that are coprime to $n$.
• A deep but accessible fact:
  • For any unit $a$ modulo $n$, $$a^{\varphi(n)} \equiv 1 \pmod{n}.$$
• This implies:
  • The order of $a$ must divide $\varphi(n)$.
• Intuition:
  • The units modulo $n$ form a group under multiplication.
  • Repeated multiplication must eventually cycle.
  • The cycle length must divide the size of the group.

Primitive Roots and When the Order Is Maximal

• A number $g$ modulo $n$ is a primitive root if: $$\text{order of } g = \varphi(n).$$
• This means $g$ generates all units modulo $n$ through its powers.
• Not every modulus has primitive roots.
• Those that do include:
  • Prime powers $p^k$ (with $p$ odd)
  • $2$, $4$, and $2p^k$ for odd prime $p$
• Primitive roots are powerful tools in number theory and cryptography.

Applications: Fast Exponentiation, Cryptography, and Beyond

• Orders appear naturally in:
  • RSA encryption (through Euler’s theorem)
  • Diffie–Hellman key exchange (uses primitive roots)
  • Pseudorandom number generators
  • Understanding cycles in modular arithmetic
• Knowing the order helps:
  • Reduce large exponents
  • Predict periodic behavior
  • Simplify computations

Common Pitfalls and Misconceptions

• Mistake: Trying to find the order of a non‑unit.
  • If $\gcd(a,n)\neq 1$, the order does not exist.
• Mistake: Assuming the order is always large.
  • Many numbers have small orders.
• Mistake: Thinking the order is the first time a power repeats.
  • It’s the first time the power equals 1, not any repeated value.
• Mistake: Confusing order with $\varphi(n)$.
  • The order divides $\varphi(n)$ but is not always equal to it.

Calculator

Exercises

1. Compute the order of $2$ modulo $7$.

   Solution

   Order of $2$ modulo $7$

   We compute powers of $2$ modulo $7$:

   • $2^1 \equiv 2 \pmod{7}$
   • $2^2 \equiv 4 \pmod{7}$
   • $2^3 \equiv 8 \equiv 1 \pmod{7}$

   The first time we get $1$ is at exponent $3$, so the order of $2$ mod $7$ is $$\operatorname{ord}_7(2) = 3.$$

2. Compute the order of $3$ modulo $10$.

   Solution

   Order of $3$ modulo $10$

   • First check $\gcd(3,10)$:
     • $\gcd(3,10) = 1$, so $3$ is a unit modulo $10$.

   Now compute powers:

   • $3^1 \equiv 3 \pmod{10}$
   • $3^2 \equiv 9 \pmod{10}$
   • $3^3 \equiv 27 \equiv 7 \pmod{10}$
   • $3^4 \equiv 21 \equiv 1 \pmod{10}$

   The first time we get $1$ is at exponent $4$, so $$\operatorname{ord}_{10}(3) = 4.$$

3. Compute the order of $5$ modulo $12$.

   Solution

   Order of $5$ modulo $12$

   • Check $\gcd(5,12)$:
     • $\gcd(5,12) = 1$, so $5$ is a unit modulo $12$.

   Compute powers:

   • $5^1 \equiv 5 \pmod{12}$
   • $5^2 \equiv 25 \equiv 1 \pmod{12}$

   We already get $1$ at exponent $2$, so $$\operatorname{ord}_{12}(5) = 2.$$

4. Compute the order of $7$ modulo $9$.

   Solution

   Order of $7$ modulo $9$

   • Check $\gcd(7,9)$:
     • $\gcd(7,9) = 1$, so $7$ is a unit modulo $9$.

   Compute powers:

   • $7^1 \equiv 7 \pmod{9}$
   • $7^2 \equiv 49 \equiv 4 \pmod{9}$ (since $49 - 45 = 4$)
   • $7^3 \equiv 7 \cdot 4 = 28 \equiv 1 \pmod{9}$

   So $$\operatorname{ord}_9(7) = 3.$$

5. Explain why a number with $\gcd(a,n)\neq 1$ cannot have an order modulo $n$.

   Solution

   Why $\gcd(a,n)\neq 1$ means no order

   • Suppose $\gcd(a,n)\neq 1$. Then $a$ and $n$ share a common factor $d>1$.
   • Any power $a^k$ will still be divisible by $d$.
   • But $1$ is not divisible by $d>1$.
   • So we can never have $a^k \equiv 1 \pmod{n}$.
   • Therefore, if $\gcd(a,n)\neq 1$, the order of $a$ modulo $n$ does not exist.
6. Give an example of a number whose order is strictly smaller than $\varphi(n)$.

   Solution

   Example where order is smaller than $\varphi(n)$

   We just saw one:

   • Take $n = 12$.
   • $\varphi(12)$ counts numbers between $1$ and $12$ that are coprime to $12$:
     • These are $1,5,7,11$, so $\varphi(12) = 4$.
   • From Exercise 3, the order of $5$ modulo $12$ is $2$.
   • So here: $$\operatorname{ord}_{12}(5) = 2 < \varphi(12) = 4.$$

   This is a concrete example where the order is strictly smaller than $\varphi(n)$.

7. True or false: If $a$ has order $k$ modulo $n$, then $a^m \equiv 1$ iff $k$ divides $m$.

   Solution

   True/false: If $a$ has order $k$ modulo $n$, then $a^m \equiv 1$ iff $k \mid m$

   This statement is true.

   • By definition, $a^k \equiv 1 \pmod{n}$ and $k$ is the smallest positive integer with this property.
   • If $k \mid m$, say $m = kq$, then $$a^m = a^{kq} = (a^k)^q \equiv 1^q \equiv 1 \pmod{n}.$$
   • Conversely, if $a^m \equiv 1 \pmod{n}$, then the minimality of $k$ implies that $m$ must be a multiple of $k$.
   • So $a^m \equiv 1 \pmod{n}$ if and only if $k$ divides $m$.
8. Find a number modulo $11$ that has order $10$. (Hint: $11$ is prime, so $\varphi(11)=10$.)

   Solution

   A number modulo $11$ with order $10$

   • Since $11$ is prime, every nonzero residue modulo $11$ is a unit.
   • We want an element of order $10 = \varphi(11)$, i.e., a primitive root modulo $11$.

   Try $2$:

   • $2^1 \equiv 2$
   • $2^2 \equiv 4$
   • $2^3 \equiv 8$
   • $2^4 \equiv 16 \equiv 5$
   • $2^5 \equiv 10$
   • $2^6 \equiv 20 \equiv 9$
   • $2^7 \equiv 18 \equiv 7$
   • $2^8 \equiv 14 \equiv 3$
   • $2^9 \equiv 6$
   • $2^{10} \equiv 12 \equiv 1 \pmod{11}$

   We only reach $1$ at exponent $10$, so $$\operatorname{ord}_{11}(2) = 10.$$ Thus, $2$ is a number modulo $11$ with order $10$.

9. For modulus $9$, list all units and compute their orders.

   Solution

   Units modulo $9$ and their orders

   • Numbers between $1$ and $9$ that are coprime to $9$:
     • $1,2,4,5,7,8$.
   • These are the units modulo $9$.

   Now compute orders:

   • For $1$:
     • $1^1 \equiv 1 \pmod{9}$, so $\operatorname{ord}_9(1) = 1$.
   • For $2$:
     • $2^1 \equiv 2$
     • $2^2 \equiv 4$
     • $2^3 \equiv 8$
     • $2^4 \equiv 16 \equiv 7$
     • $2^5 \equiv 14 \equiv 5$
     • $2^6 \equiv 10 \equiv 1 \pmod{9}$
     So $\operatorname{ord}_9(2) = 6$.
   • For $4$:
     • $4^1 \equiv 4$
     • $4^2 \equiv 16 \equiv 7$
     • $4^3 \equiv 28 \equiv 1 \pmod{9}$
     So $\operatorname{ord}_9(4) = 3$.
   • For $5$:
     • $5^1 \equiv 5$
     • $5^2 \equiv 25 \equiv 7$
     • $5^3 \equiv 35 \equiv 8$
     • $5^4 \equiv 40 \equiv 4$
     • $5^5 \equiv 20 \equiv 2$
     • $5^6 \equiv 10 \equiv 1 \pmod{9}$
     So $\operatorname{ord}_9(5) = 6$.
   • For $7$:
     • Already computed in Exercise 4: $\operatorname{ord}_9(7) = 3$.
   • For $8$:
     • $8 \equiv -1 \pmod{9}$.
     • $8^2 \equiv (-1)^2 = 1 \pmod{9}$.
     • $8^1 \not\equiv 1$, so $\operatorname{ord}_9(8) = 2$.

   Summary:

   • $\operatorname{ord}_9(1) = 1$
   • $\operatorname{ord}_9(2) = 6$
   • $\operatorname{ord}_9(4) = 3$
   • $\operatorname{ord}_9(5) = 6$
   • $\operatorname{ord}_9(7) = 3$
   • $\operatorname{ord}_9(8) = 2$
10. Show that if $a$ has order $k$ modulo $n$, then $a^m$ has order $\frac{k}{\gcd(k,m)}$.

    Solution

    If $a$ has order $k$ modulo $n$, show $a^m$ has order $\dfrac{k}{\gcd(k,m)}$

    Let $a$ be a unit modulo $n$ with order $k$, and let $d = \gcd(k,m)$.

    • Write $k = d \cdot k'$ and $m = d \cdot m'$ with $\gcd(k',m') = 1$.
    • Consider $b = a^m$.
    • We want the smallest positive integer $t$ such that $$b^t \equiv 1 \pmod{n}.$$
    • But $$b^t = (a^m)^t = a^{mt}.$$
    • So we need $a^{mt} \equiv 1 \pmod{n}$.
    • Since $a$ has order $k$, we know:
      • $a^{mt} \equiv 1 \pmod{n}$ iff $k \mid mt$.

    Now use the factorization:

    • $k \mid mt$ means $d k' \mid d m' t$, so $k' \mid m' t$.
    • Because $\gcd(k',m') = 1$, the only way $k'$ divides $m' t$ is if $k'$ divides $t$.
    • So the smallest positive $t$ with this property is $t = k'$.

    Recall $k' = \dfrac{k}{d} = \dfrac{k}{\gcd(k,m)}$, so the order of $a^m$ is $$\operatorname{ord}_n(a^m) = \frac{k}{\gcd(k,m)}.$$